package allsort;

public class Sort {
    //插入排序
    /*
    时间复杂度  : 最好情况  : 数据有序的情况下 ,O(N)
    最坏情况  : 数据逆序的时候  : O(N^2)
    空间复杂度 O(1)
    稳定性  : 稳定的
    一个本身就不稳定的排序,是不可能变成稳定的  排序
    但是一个本身就稳定的排序  是可以实现为不稳定的排序的
    特点: 数据越趋于排序  ,直接插入排序就越快
    */

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i -1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    //直接跳出循环
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /*
    希尔排序
    稳定性 :  不稳定
    时间复杂度 一般在O(n^1.5)到 O(n^2) 之间  最优 在O(n^1.3)
    空间复杂度 : O(1)
      变形的插入排序  有间隔

    */

    public  static  void  shellSort(int[] array){
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 2;
            shell(array,gap);
        }
    }
    public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (;j >= 0; j--) {
                if (array[j] > tmp) {
                    //换
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+ gap] = tmp;
        }
    }

    /*
    选择排序
    时间复杂度 :  O(N^2)
    空间复杂度 : O(1)
    稳定性不稳定
    */
    public static void selectSort (int[] array) {
        for (int i = 0; i < array.length; i++) {
            //记录一下最小元素的下标
            int minIndex = i;
            int j = i + 1;
            for (; j < array.length; j++) {
                if (array[j] < array[i]) {
                    minIndex = j;
                }
            }
            //最后交换下标对应的元素\
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array,int i , int j) {
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }

    //选择排序第二种实现方式
    public static void selectSort2 (int[] array) {
        int left = 0;
        int right = array.length -1;
        while (left <  right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }

                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            //交换
            swap(array,minIndex,left);
            //第一次交换 如果 最大值可能是left下标的   会把最大值换跑
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }

    }
    public static void main(String[] args) {
        int[] arr = {1,6,2,4,2};
        //insertSort(arr);

        //selectSort(arr);
        selectSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
